#include<iostream>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
typedef long long LL;
int in, out;
string s;
char temp[63];
LL get_10jinzhi(int in ,string s)
{
	LL ans = 0;
	int k = s.size();
	for (int i = 0; i < s.size(); i++) {
		ans = ans + (s[i] - '0') * pow(in, k - 1);
		k--;
	}
	return ans;
}
void change(int out, LL ans)
{
	vector<char>ans1;
	while (ans) {
		int k = ans % out;
		ans1.push_back(temp[k]);
		//cout << temp[k];
		ans /= out;
	}
	cout << ans1.size() << endl;
	for (int i = ans1.size() - 1; i >= 0; i--) {
		cout << ans1[i];
	}
}
void init_temp()
{
	int k = 0;
	for (int i = 0; i < 10; i++) {
		temp[k++] = (char)(i + '0');
	}
	for (int i = 'A'; i <= 'Z'; i++) {
		temp[k++] = (char)(i);
	}
	for (int i = 'a'; i <= 'z'; i++) {
		temp[k++] = (char)(i);
	}
}
int main()
{
	int t;
	cin >> t;
	init_temp();
	while (t--) {
		cin >> in >> out;
		cin >> s;
		LL ret = get_10jinzhi(in, s);
		cout << "ret====" << ret << endl;
		change(out, ret);
		cout << endl;
	}
	return 0;
}